package arithmetic2;

import java.util.Arrays;

/**
 * Created by AJie on 2019/7/30
 * Function :https://leetcode-cn.com/problems/3sum-closest/
 *  与3sum 类似
 *
 */
public class T_016_3SumClosest {


    public static void main(String[] args) {
        int i = threeSumClosest(new int[]{-1, 2, 1, -4}, 1);
        System.out.println(i);
    }

    public static int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        if (len <3){
            return 0;
        }
        Arrays.sort(nums);
        int res = nums[0]+nums[1]+nums[2];
        for (int i = 0; i < len; i++) {
            if (i>0 && nums[i-1]==nums[i])continue;
            int L = i+1;
            int R = len-1;
            while (L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if (Math.abs(sum-target) < Math.abs(res-target)){
                    res = sum;
                }
               if (sum>target){
                    R--;
                }else if (sum <target){
                    L++;
                }else {
                    return res;
               }
            }
        }
        return res;
    }

    public static int threeSumClosest2(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.length;i++) {
            int start = i+1, end = nums.length - 1;
            while(start < end) {
                int sum = nums[start] + nums[end] + nums[i];
                if(Math.abs(target - sum) < Math.abs(target - ans))
                    ans = sum;
                if(sum > target)
                    end--;
                else if(sum < target)
                    start++;
                else
                    return ans;
            }
        }
        return ans;
    }

}
